package com.hy.backtracking2;

import java.util.ArrayList;
import java.util.List;

public class IpAddressesHandler {


    /**
     * 93.复原IP地址
     * 力扣题目链接
     *
     * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
     *
     * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     *
     * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
     *
     * 示例 1：
     *
     * 输入：s = "25525511135"
     * 输出：["255.255.11.135","255.255.111.35"]
     */

    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    //方法二：比上面的方法时间复杂度低，更好地剪枝，优化时间复杂度
    public List<String> restoreIpAddresses(String str){
        restoreIpAddressesHandler(str,0,0);
        return res;
    }

    // number表示stringbuilder中ip段的数量
    public void restoreIpAddressesHandler(String str,int start,int num){
        if (start == str.length() && num == 4){
            res.add(sb.toString());
            return;
        }
        // 如果start等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是start小于s的长度，则直接返回
        if (start == str.length() || num == 4){
            return;
        }

        // 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
        for (int i = start; i < str.length() && i - start < 3 && Integer.parseInt(str.substring(start, i + 1)) >= 0
                && Integer.parseInt(str.substring(start, i + 1)) <= 255; i++) {
            // 如果ip段的长度大于1，并且第一位为0的话，continuezz
            if (i+1 - start > 1 && str.charAt(start) - '0' == 0){
                continue;
            }
            sb.append(str.substring(start,i+1));
            // 当stringBuilder里的网段数量小于3时，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点
            if (num < 3){
                sb.append(".");
            }
            num++;
            restoreIpAddressesHandler(str,i+1,num);
            num--;
            // 删除当前stringBuilder最后一个网段，注意考虑点的数量的问题
            sb.delete(start+num,i+num+2);
        }
    }

    public static void main(String[] args) {
        IpAddressesHandler ip = new IpAddressesHandler();
        String str = "25525511135";
        System.out.println("res: "+ip.restoreIpAddresses(str));
    }
}
